package leetcode_1100;

import java.math.BigInteger;

/**
 *@author 周杨 
 *SmallestIntegerDivisibleByK_1022 给一个正整数 问它能否被每位都是1的正整数整除 如果可以 输出这个正整数有多少个1
 *describe:AC 100% 一个数如果能整除一个数 那么不要让它超过这个数 
 *2019年3月24日 上午11:33
 */
public class SmallestIntegerDivisibleByK_1022 {
	public static void main(String[] args) {
		SmallestIntegerDivisibleByK_1022 test = new SmallestIntegerDivisibleByK_1022();
		System.out.println(test.smallestRepunitDivByK(17));
	}
	//技巧 一个数如果能整除一个数 那么取余也一定能整除这个数
	public int smallestRepunitDivByK(int K) {
		if (K % 2 == 0 || K % 5 == 0) return -1;
        int r = 0;
        //一个数如果循环了最大k次 都没有找到答案  那么就是没有答案
        for (int N = 1; N <= K; ++N) {
            r = (r * 10 + 1) % K;
            if (r == 0) return N;
        }
        return -1;
	}

	// 大数处理 超时
	public int smallestRepunitDivByK1(int K) {
		if (K % 2 == 0 || K % 5 == 0)
			return -1;
		BigInteger one = new BigInteger("1");
		BigInteger pos = new BigInteger("1");
		BigInteger div = new BigInteger(String.valueOf(K));
		BigInteger zero = new BigInteger("0");
		BigInteger ten = new BigInteger("10");
		int res = 1;
		while (!pos.mod(div).equals(zero)) {
			pos = pos.multiply(ten);
			pos = pos.add(one);
			++res;
		}
		return res;
	}

}
